﻿#pragma once
#include <iostream>

#include <string>
#include <vector>
using namespace std;



// 哈希函数采用除留余数法﻿
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
enum State
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
	HashTable()
		:_tables(__stl_next_prime(0))
		,_n(0)
	{}
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] = {
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917, 25165843,
			50331653, 100663319, 201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
	bool Insert(const pair<K, V>& kv)
	{
		if (_n*10 / _tables.size() >= 7)
		{
			HashTable<K,V> newtables;
			newtables._tables.resize(__stl_next_prime(_tables.size() + 1));
			for (auto& e : _tables)
			{
				if (e._state == EXIST)
				{
					newtables.Insert(e._kv);
				}
			}
			_tables.swap(newtables._tables);
		}
		if (Find(kv.first))
			return false;
		Hash hashfunc;
		size_t hash0 = hashfunc(kv.first) % _tables.size();
		size_t hashi = hash0;
		size_t i = 1;
		while (_tables[hashi]._state == EXIST)
		{
			hashi = (hash0 + i) % _tables.size();
			++i;
		}
		_tables[hashi]._kv = kv;
		_tables[hashi]._state = EXIST;
		_n++;
		return true;
	}
	HashData<K, V>* Find(const K& key)
	{
		//size_t hash0 = key % _tables.size();
		Hash hashfunc;
		size_t hash0 = hashfunc(key) % _tables.size();

		size_t hashi = hash0;
		size_t i = 1;
		while (_tables[hashi]._state != EMPTY)
		{
			if (_tables[hashi]._state == EXIST
				&& _tables[hashi]._kv.first == key)
			{
				return &_tables[hashi];
			}

			hashi = (hash0 + i) % _tables.size();
			++i;
		}

		return nullptr;
	}
	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			return true;
		}
		else
		{
			return false;
		}
	}

private:
	vector<HashData<K, V>> _tables;
	size_t _n;  
};




